90. 子集 II

Similar Question

Solution Tips

方案一: 回溯 + N 叉树思路 + 跳过重复

var subsetsWithDup = function(nums) {
    // 又是跳过重复
    const res = [];
    nums.sort((a, b) => a - b);
    dfs([], 0);
    return res;


    function dfs(chosen, index) {
        res.push([...chosen])

        if (index === nums.length) {
            return;
        }

        // for 循环的形式比较适合处理跳过重复, 二元思路得记录 used 了
        for (let i = index; i < nums.length; i++) {
            chosen.push(nums[i]);
            dfs(chosen, i + 1);
            chosen.pop();

            while (nums[i] === nums[i + 1]) i++;
        }
    }
};
console.log(subsetsWithDup([4,4,4,1,4]));

方案二: 回溯 + 二元思路 + choosePre

其实不需要使用 used, 只需要记住前一个是否相同就行, 如果是相同的数就跳过, 保证相同的数只选择了一次

var subsetsWithDup = function(nums) {
    nums.sort((a, b) => a - b);
    let t = [], ans = [];
    const dfs = (choosePre, cur, nums) => {
        if (cur === nums.length) {
            ans.push(t.slice());
            return;
        }
        dfs(false, cur + 1, nums);
        if (!choosePre && cur > 0 && nums[cur - 1] === nums[cur]) {
            return;
        }
        t.push(nums[cur]);
        dfs(true, cur + 1, nums);
        t = t.slice(0, t.length - 1);
    }
    dfs(false, 0, nums);
    return ans;
};